/**
 * @file   BinaryTree.h
 * @author zhang-zh
 * @date   Friday Dec.4 2020
 * 
 * @brief  A header files for binary trees.
 * 
 */

#ifndef __zhangbianrytree__
#define __zhangbinarytree__

#define BLACK false
#define RED true

#include <iostream>
#include <vector>
#include <limits>
#include <iomanip>
#include <algorithm>
#include <queue>

#define MIN (std::numeric_limits<TYPE>::min())

template <class TYPE>
class BinaryTree;

template <class TYPE>
class BinaryTree
{
public:
    /**
     * The node structure of the binary tree. Set all members as public
     * for efficiency.
     * 
     */
    class BinaryTreeNode;

    typedef BinaryTreeNode Node;
    
    class BinaryTreeNode
    {
    public:
	TYPE data;		/**< Satellite data, which is
				 * also a key value. */
	BinaryTreeNode *left;	/**< Left child. */
	BinaryTreeNode *right;	/**< Right child. */
	BinaryTreeNode *parent;	/**< Parent.  */

    bool color = RED;     
    /** 
	 * Default constructor. 
	 * 
	 */
	BinaryTreeNode(){};

	/** 
	 * Constructor. Copy a node from the given const address.
	 * 
	 * @param _t The const address point to a node(can not be a
	 * NULL).
	 */
	BinaryTreeNode(const BinaryTreeNode *_t)
	{
	    if (_t == NULL)
	    {
		std::cerr << "Error! Can not copy a NULL."<< std::endl;
		std::exit(-1);
	    }
	    data = _t->data;
	    parent = left = right = NULL;
	};

	/** 
	 * Constructor. Copy a node from the given address.
	 * 
	 * @param _t The address point to a node(can not be a NULL).
	 */
	BinaryTreeNode(BinaryTreeNode *_t)
	{
	    if (_t == NULL)
	    {
		std::cerr << "Error! Can not copy a NULL."<< std::endl;
		std::exit(-1);
	    }
	    data = _t->data;
	    parent = left = right = NULL;
	};

	/** 
	 * Constructor. Create a node with the data is the given
	 * value _d.
	 * 
	 * @param _d Given value.
	 */
	BinaryTreeNode(TYPE _d)
	{
	    data = _d;
	    parent = left = right = NULL;
	};

	/** 
	 * Destructor.
	 * 
	 */
	~BinaryTreeNode(){};
    };

protected:
    Node *root;  /** The address of the root node. */
    Node *nil;  /** The sentinel node. */

public:
     /** 
     * Default constructor.
     * 
     */
    BinaryTree()
    {
	nil = new Node;
    nil->data = MIN;
    nil->color = BLACK;
	this->root = nil;
    }

     /** 
     * Constructor. Create a new tree with only one root node, which
     * the the data inside is the given value _new.
     * 
     * @param _new Given value.
     */
    BinaryTree(TYPE _new);

    ~BinaryTree();

    /** 
     * Inorder walking and printing the sub-tree root at _x.
     * 
     * @param _x The root of the sub-tree.
     * 
     */
    void inorder_walk(const Node *_x) const;

    /** 
     * Inorder walking and printing the whole tree from the root.
     * 
     * 
     */
    void inorder_walk() const;

    /** 
     * Seach the location of the node contains data _d. If there are
     * more than one nodes, return the first one met. 
     * 
     * @param _d The data for searching.
     * 
     * @return The address of the node contains _d, and nil if not
     * found.
     */
    Node *search(TYPE _d);

    /** 
     * Find the node whose data is the minimum in the whole tree.
     * 
     * 
     * @return The address of the node with the minimum.
     */
    Node *min();

    /** 
     * Find the node whose data is the minimum under the node _x.
     * 
     * 
     * @return The address of the node with the minimum.
     */
    Node *min(Node *_x);

    /** 
     * Find the node whose data is the maximum in the whole tree.
     * 
     * 
     * @return The address of the node with the maximum.
     */
    Node *max();

    /** 
     * Find the node whose data is the maximum under the node _x.
     * 
     * 
     * @return The address of the node with the maximum.
     */
    Node *max(Node *_x);

    /** 
     * Delete the whole sub-tree root at _x, and release the memory.
     * 
     * @param _x The root of the sub-tree.
     * 
     */
    void release(Node *_x);

    /** 
     * Delete the whole tree and release the memory.
     * 
     * 
     */
    void release();

    /** 
     * Trans plant the sub-tree root at _u to _v. 
     * 
     * @param _u The root of the source sub-tree.
     * @param _v The root place of the sub-tree trans planting to.
     * 
     */
    void transplant(Node *_u, Node *_v);

    /**
     * Rotate the tree with the root _x on the right 
     * to keep ballance.
     * 
     * @param _x The basic node of the operation.
     * 
     */
    void RightRotate(Node *_x);

    /**
     * Rotate the tree with the root _x on the left
     * to keep ballance.
     * 
     * @param _x The basic node of the operation.
     * 
     */
    void LeftRotate(Node *_x);

    /** 
     * Find the node with the smallest data greater than the data of
     * _x.
     * 
     * @param _x The start node.
     * 
     * @return The address of the successor node.
     */
    Node *successor(Node *_x);

    /** 
     * Find the node with the largest data less than the data of
     * _x.
     * 
     * @param _x The start node.
     * 
     * @return The address of the predecessor node.
     */
    Node *predecessor(Node *_x);

    /** 
     * Insert a new node to the binary search tree, and keep it as
     * a binary search tree.
     * 
     * @param _new The new node.
     * 
     */
    void insert(Node *_new);
    
    /** 
     * Insert a new node with data _d to the binary search tree, and
     * keep it as a binary search tree.
     * 
     * @param _new The data for the new node.
     * 
     */
    void insert(TYPE _d);

    /** 
     * Delete node _x in the binary search tree, and keep it as a
     * binary search tree.
     * 
     * @param _x The node to delete.
     * 
     */
    void del(Node *_x);
};

template <class TYPE>
BinaryTree<TYPE>::BinaryTree(TYPE _new)
{
    nil = new Node;
    nil->data = MIN;
    nil->color = BLACK;
    Node *r = new Node;
    r->data = _new;
    r->left = nil;
    r->right = nil;
    r->parent = nil;
    this->root = r;
}

template <class TYPE>
void BinaryTree<TYPE>::inorder_walk(const Node *_x) const
{
    if (_x != nil)
    {
	inorder_walk(_x->left);
	std::cout << _x->data << " ";
	inorder_walk(_x->right);
    }
}

template <class TYPE>
void BinaryTree<TYPE>::inorder_walk() const
{
    inorder_walk(this->root);
}

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::search(TYPE _d)
{
    Node *x = this->root;
    while (x != this->nil && _d != x->data)
	// Here the decision rule has to accord with the one in the
	// insert function.
    	if (_d < x->data)
    	    x = x->left;
    	else
    	    x = x->right;
    return x;
};

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::min()
{
    Node *x = this->root;
    if (x != this->nil)
	while (x->left != this->nil)
	    x = x->left;
    return x;
}

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::max()
{
    Node *x = this->root;
    if (x != this->nil)
	while (x->right != this->nil)
	    x = x->right;
    return x;
}

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::min(Node *_x)
{
    if (_x != this->nil)
	while (_x->left != this->nil)
	    _x = _x->left;
    return _x;
}

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::max(Node *_x)
{
    if (_x != this->nil)
	while (_x->right != this->nil)
	    _x = _x->right;
    return _x;
}

template <class TYPE>
void BinaryTree<TYPE>::release(Node *_x)
{
    if(_x != nil)
    {
        release(_x->left);
        release(_x->right);
        delete _x;
    }
}

template <class TYPE>
void BinaryTree<TYPE>::release()
{
    release(this->root);
    delete nil;
}

template <class TYPE>
void BinaryTree<TYPE>::transplant(Node* _u, Node* _v)
{
    if (_u == nil)
    {
	std::cerr << "Error! Can not transplant to a NULL." << std::endl;
	std::exit(-1);
    }
    if (_u->parent == nil)
	root = _v;   /// Here can not use _u = _v;
    else if (_u == _u->parent->left)
	_u->parent->left = _v;
    else
	_u->parent->right = _v;
    // if (_v != nil)
    _v->parent = _u->parent;
}

template <class TYPE>
BinaryTree<TYPE>::~BinaryTree()
{
    release();
}

template <class TYPE>
void BinaryTree<TYPE>::LeftRotate(Node *_x)
{
    Node *y = _x->right;
    _x->right = y->left;
    if (y->left != nil)
	y->left->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
	root = y;
    // if _x is _x's parent's left child,
    else if (_x == _x->parent->left)
	// set y as _x's parent's left child.
	_x->parent->left = y;
    else
	_x->parent->right = y;
    y->left = _x;
    _x->parent = y;
}

template <class TYPE>
void BinaryTree<TYPE>::RightRotate(Node *_x)
{
    Node *y = _x->left;
    _x->left = y->right;
    if (y->right != nil)
	y->right->parent = _x;
    y->parent = _x->parent;
    if (_x->parent == nil)
	root = y;
    // if _x is _x's parent's left child,
    else if (_x == _x->parent->left)
	// set y as _x's parent's left child.
	_x->parent->left = y;
    else
	_x->parent->right = y;
    y->right = _x;
    _x->parent = y;
}

template <class TYPE> 
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::successor(Node *_x)
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	return NULL;
    }
    if (_x->right != this->nil)
	return min(_x->right);
    Node *y = _x->parent;
    while (y != this->nil && _x == y->right)
    {
	_x = y;
	y = y->parent;
    }
    return y;
}

template <class TYPE>
typename BinaryTree<TYPE>::Node *BinaryTree<TYPE>::predecessor(Node *_x)
{
    if (_x == this->nil)
    {
	std::cerr << "Error! The node is a NULL." << std::endl;
	return NULL;
    }

    if (_x->left != this->nil)
	return max(_x->left);
    Node *y = _x->parent;
    while (y != this->nil && _x == y->left)
    {
	_x = y;
	y = y->parent;
    }
    return y;
}

template <class TYPE>
void BinaryTree<TYPE>::insert(Node *_new)
{
    Node *y = this->nil;
    Node *x = this->root;
    // Make sure that _new is a single node binary tree.
    _new->left = _new->right = this->nil;
    while (x != this->nil)
    {
	y = x;
	// The nodes less than to the left, then these greater than or
	// equal to to the right.
	if (_new->data < x->data)
	    x = x->left;
	else
	    x = x->right;
    }
    _new->parent = y;
    if (y == this->nil)
	this->root = _new;
    // Here the decision rule has to same as above.
    else if (_new->data < y->data)
	y->left = _new;
    else
	y->right = _new;
}

template <class TYPE>
void BinaryTree<TYPE>::insert(TYPE _d)
{
    Node *y = this->nil;
    Node *x = this->root;
    Node *z = new Node(_d);
    // Here has to reset the nil, since the Node do not contains the
    // definatio of nil.
    z->left = z->right = this->nil;
    while (x != this->nil)
    {
    	y = x;
	// The nodes less than to the left, then these greater than or
	// equal to to the right.
    	if (z->data < x->data)
    	    x = x->left;
    	else
    	    x = x->right;
    }
    z->parent = y;
    if (y == this->nil)
    	this->root = z;
    // Here the decision rule has to same as above.
    else if (z->data < y->data)
    	y->left = z;
    else
    	y->right = z;
}

template<class TYPE>
void BinaryTree<TYPE>::del(Node *_x)
{
    if(_x->left == nil)
    {
        transplant(_x, _x->right);
    }
    else if(_x->right == nil)
    {
        transplant(_x, _x->left);
    }
    else
    {
	Node *y = min(_x->right);
	if (y->parent != _x)   
	{
	    this->transplant(y, y->right);
	    y->right = _x->right;
	    y->right->parent = y;
	}
	this->transplant(_x, y);
	y->left = _x->left;
	y->left->parent = y;
    }
    delete _x;
}

#else 
//do nothing.
#endif